package leetcode;

public class Search2DMatrix {

	public static void main(String[] args) {
		int[][] matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6,9, 16, 22},{3,6,9,16,22},{18,21,23,26,30}};
		Search2DMatrix object = new Search2DMatrix();
		System.out.println(object.searchMatrix2(matrix, 0));
	}
	
	//每一行都是排序的
	//并且下一行的第一个数大于上一行的最后一个数
	
//	Integers in each row are sorted from left to right.
//	The first integer of each row is greater than the last integer of the previous row.
	
	public boolean searchMatrix(int[][] matrix, int target) {
		if (matrix == null || matrix.length <= 0) {
			return false;
		}
		int rows = matrix.length;
		int cols = matrix[0].length;
		int low = 0;
		int high = rows * cols - 1;
		int middle = 0;
		int rowIndex = 0, colIndex = 0;
		while (low <= high) {
			middle = low + (high - middle) / 2;
			rowIndex = middle / cols;
			colIndex = middle % cols;
			if (matrix[rowIndex][colIndex] == target) {
				return true;
			} else if (matrix[rowIndex][colIndex] > target) {
				high = middle - 1;
			} else {
				low = middle + 1;
			}
		}
		return false;
	}
	
	
	//每一行是递增。每一列是递增，但不保证下一行的第一个数大于上一行的最后一个数
    public boolean searchMatrix2(int[][] matrix, int target) {
    	if(matrix == null || matrix.length <= 0){
    		return false;
    	}
    	int m = matrix.length;
    	int n = matrix[0].length;
    	
    	if(n == 0){
    	    return false;
    	}
    	int[] arr = new int[m];
    	for (int i = 0; i < m; i++) {
			arr[i] = matrix[i][0];
		}
    	int rowIndex = binarySearch(arr, 0, m - 1, target);
    	int columnIndex = binarySearch(matrix[0], 0, n - 1, target);
    	
    	for (int i = 0; i <= rowIndex; i++) {
    		//如果该行最大值都小于target
    		if(matrix[i][n - 1] < target){
    			continue;
    		}
			if(binarySearch2(matrix[i], 0, columnIndex, target)){
				return true;
			}
		}
    	return false;
    }
    
    //找到小于等于target的最大下标
    public int binarySearch(int[] array, int left, int right, int target){
    	if(array == null || array.length <= 0 || left > right || left < 0 || right >= array.length){
    		return -1;
    	}
    	if(array[left] > target){
    		return -1;
    	}
    	int middle = 0;
    	while(left < right - 1){
    		middle = left + (right - left) / 2;
    		if(array[middle] <= target){
    			left = middle;
    		}else{
    			right = middle;
    		}
    	}
    	if(array[right] <= target){
    		return right;
    	}else{
    		return left;
    	}
    }
    
    //数组中是否有target
    public boolean binarySearch2(int[] array, int left, int right, int target){
    	if(array == null || array.length <= 0 || left > right || left < 0 || right >= array.length){
    		return false;
    	}
    	if(array[left] > target){
    		return false;
    	}
    	int middle = 0;
    	while(left <= right){
    		middle = left + (right - left) / 2;
    		if(array[middle] == target){
    			return true;
    		}else if(array[middle] > target){
    			right = middle - 1;
    		}else{
    			left = middle + 1;
    		}
    	}
    	return false;
    }
    
    //O(m + n)的做法
    public boolean searchMatrix2_2(int[][] matrix, int target) {
        if(matrix == null || matrix.length < 1 || matrix[0].length <1) {
            return false;
        }
        int col = matrix[0].length-1;
        int row = 0;
        while(col >= 0 && row <= matrix.length-1) {
            if(target == matrix[row][col]) {
                return true;
            } else if(target < matrix[row][col]) {
                col--;
            } else if(target > matrix[row][col]) {
                row++;
            }
        }
        return false;
    }
}
